package algotithm.weekendrace.leetcode227.test4;

import java.util.TreeSet;

/**
 * @author zhouyanxiang
 * @Date 2021-02-2021/2/7-18:31
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {5,-7,3,5};
        int goal = 6;
        int i = solution.minAbsDifference(nums, goal);
        System.out.println(i);
    }

    public int minAbsDifference(int[] nums, int goal) {
        int n = nums.length, l = n / 2, r = n - l, L = 1 << l, R = 1 << r;
        TreeSet<Integer> set = new TreeSet();
        int[] dpl = new int[L], dpr = new int[R];
        int[] nums2 = new int[r];
        for(int i = 0; i < r; i++) {
            nums2[i] = nums[i + l];
        }
        for(int i = 1; i < L; i++) {
            int pre = i & (i - 1);
            int ind = i - pre;
            dpl[i] = dpl[pre] + nums[(int)Math.round(Math.log(ind) / Math.log(2))];
            set.add(dpl[i]);
        }
        set.add(0);
        for(int i = 1; i < R; i++) {
            int pre = i & (i - 1);
            int ind = i - pre;
            dpr[i] = dpr[pre] + nums2[(int)Math.round(Math.log(ind) / Math.log(2))];
        }
        int res = Math.abs(goal);
        for(int i = 0; i < R; i++) {
            Integer floor = set.floor(goal - dpr[i]), ceil = set.ceiling(goal - dpr[i]);
            if(floor != null) {
                res = Math.min(res, Math.abs(floor + dpr[i] - goal));
            }
            if(ceil != null) {
                res = Math.min(res, Math.abs(ceil + dpr[i] - goal));
            }
        }
        return res;
    }
}
